package DataStructure.tree;

import java.util.ArrayDeque;
import java.util.Queue;

/**
 * 104. 二叉树的最大深度 https://leetcode.cn/problems/maximum-depth-of-binary-tree
 * 题目简述：给定一个二叉树，找出其最大深度。
 */
public class MaxDepth {

    /**
     * 思路一：递归法，树的最大深度为左右子树中的最大深度+1
     */
    public int maxDepth(TreeNode root) {
        if(root == null) return 0;
        int leftMaxH = maxDepth(root.left);
        int rightMaxH = maxDepth(root.right);
        return Math.max(leftMaxH, rightMaxH) + 1;
    }


    /**
     * 思路二：层序遍历，while循环中每次遍历一层，记录层数
     */
    public int maxDepth2(TreeNode root) {
        if(root == null) return 0;
        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.add(root);
        int h = 0;
        while(!queue.isEmpty()) {
            h++;
            int ln = queue.size();
            for(int i=0;i < ln;i++) {
                TreeNode node = queue.remove();
                if(node.left != null) queue.add(node.left);
                if(node.right != null) queue.add(node.right);
            }
        }
        return h;
    }
}
